package main

// 大根堆

// 调整堆：筛选法，假设 1-n 都已经是堆了，将 0 - n变为堆，
// 也就是只有堆顶不满足堆，进行调整
// rootIndex: 根索引。end: 堆最后一位元素的索引
func HeadAdjust(nums []int, rootIndex, end int) {
	rootValue := nums[rootIndex]
	// 计算左子节点: subIndex, 可以直接使用 for循环
	for subIndex := rootIndex*2 + 1; subIndex <= end; subIndex = subIndex*2 + 1 {
		// 判断左右子节点哪个大
		if subIndex < end &&
			nums[subIndex] < nums[subIndex+1] {
			subIndex++
		}
		// 比较判断，交换调整, 找到位置，结束循环
		if rootValue < nums[subIndex] {
			nums[rootIndex] = nums[subIndex]
			// 更新坐标
			rootIndex = subIndex
		} else {
			break
		}
	}
	// 赋值到正确位置
	nums[rootIndex] = rootValue
}

// 创建堆
// 根据堆的性质（完全二叉树）， [n / 2 + 1, n] 的节点都是叶子结点， 然后开始调整
// 下标从 0 开始，也就是 n / 2 到 n - 1 的节点都是叶子结点
func CreateHeap(nums []int) {
	n := len(nums)
	for i := n/2 - 1; i >= 0; i-- {
		HeadAdjust(nums, i, n-1)
	}
}

// 堆排序
func HeapSort(nums []int) {
	// 建立堆
	CreateHeap(nums)
	// 依次调整堆
	n := len(nums)
	for i := n - 1; i > 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		HeadAdjust(nums, 0, i-1)
	}
}

// 删除堆顶元素， 添加堆内元素 还有很多，这里没实现
// python 版本实现的有： https://blog.csdn.net/pythonstrat/article/details/119378788?spm=1001.2014.3001.5501
